
<!DOCTYPE html>

<html>
  
<!-- Mirrored from docs.sympy.org/latest/modules/physics/quantum/shor.html by HTTrack Website Copier/3.x [XR&CO'2014], Sat, 15 Jan 2022 03:27:46 GMT -->
<!-- Added by HTTrack --><meta http-equiv="content-type" content="text/html;charset=utf-8" /><!-- /Added by HTTrack -->
<head>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" /><meta name="generator" content="Docutils 0.17.1: http://docutils.sourceforge.net/" />

    <title>Shor’s Algorithm &#8212; SymPy 1.9 documentation</title>
    <link rel="stylesheet" type="text/css" href="../../../_static/pygments.css" />
    <link rel="stylesheet" type="text/css" href="../../../_static/default.css" />
    <link rel="stylesheet" type="text/css" href="../../../_static/graphviz.css" />
    <link rel="stylesheet" type="text/css" href="../../../_static/plot_directive.css" />
    <link rel="stylesheet" type="text/css" href="../../../../../live.sympy.org/static/live-core.css" />
    <link rel="stylesheet" type="text/css" href="../../../../../live.sympy.org/static/live-autocomplete.css" />
    <link rel="stylesheet" type="text/css" href="../../../../../live.sympy.org/static/live-sphinx.css" />
    
    <script data-url_root="../../../" id="documentation_options" src="../../../_static/documentation_options.js"></script>
    <script src="../../../_static/jquery.js"></script>
    <script src="../../../_static/underscore.js"></script>
    <script src="../../../_static/doctools.js"></script>
    <script src="../../../../../live.sympy.org/static/utilities.js"></script>
    <script src="../../../../../live.sympy.org/static/external/classy.js"></script>
    <script src="../../../../../live.sympy.org/static/live-core.js"></script>
    <script src="../../../../../live.sympy.org/static/live-autocomplete.js"></script>
    <script src="../../../../../live.sympy.org/static/live-sphinx.js"></script>
    
    <link rel="shortcut icon" href="../../../_static/sympy-notailtext-favicon.ico"/>
    <link href="shor.html" rel="canonical" />
    
    <link rel="index" title="Index" href="../../../genindex.html" />
    <link rel="search" title="Search" href="../../../search.html" />
    <link rel="next" title="Particle in a Box" href="piab.html" />
    <link rel="prev" title="Qubit" href="qubit.html" /> 
  </head><body>
    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../../../genindex.html" title="General Index"
             accesskey="I">index</a></li>
        <li class="right" >
          <a href="../../../py-modindex.html" title="Python Module Index"
             >modules</a> |</li>
        <li class="right" >
          <a href="piab.html" title="Particle in a Box"
             accesskey="N">next</a> |</li>
        <li class="right" >
          <a href="qubit.html" title="Qubit"
             accesskey="P">previous</a> |</li>
        <li class="nav-item nav-item-0"><a href="../../../index.html">SymPy 1.9 documentation</a> &#187;</li>
          <li class="nav-item nav-item-1"><a href="../../index.html" >SymPy Modules Reference</a> &#187;</li>
          <li class="nav-item nav-item-2"><a href="../index.html" >Physics</a> &#187;</li>
          <li class="nav-item nav-item-3"><a href="index.html" accesskey="U">Quantum Mechanics</a> &#187;</li>
        <li class="nav-item nav-item-this"><a href="#">Shor’s Algorithm</a></li> 
      </ul>
    </div>  

    <div class="document">
      <div class="documentwrapper">
        <div class="bodywrapper">
          <div class="body" role="main">
            
  <section id="module-sympy.physics.quantum.shor">
<span id="shor-s-algorithm"></span><h1>Shor’s Algorithm<a class="headerlink" href="#module-sympy.physics.quantum.shor" title="Permalink to this headline">¶</a></h1>
<p>Shor’s algorithm and helper functions.</p>
<p>Todo:</p>
<ul class="simple">
<li><p>Get the CMod gate working again using the new Gate API.</p></li>
<li><p>Fix everything.</p></li>
<li><p>Update docstrings and reformat.</p></li>
</ul>
<dl class="py class">
<dt class="sig sig-object py" id="sympy.physics.quantum.shor.CMod">
<em class="property"><span class="pre">class</span> </em><span class="sig-prename descclassname"><span class="pre">sympy.physics.quantum.shor.</span></span><span class="sig-name descname"><span class="pre">CMod</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="o"><span class="pre">*</span></span><span class="n"><span class="pre">args</span></span></em>, <em class="sig-param"><span class="o"><span class="pre">**</span></span><span class="n"><span class="pre">kwargs</span></span></em><span class="sig-paren">)</span><a class="reference external" href="https://github.com/sympy/sympy/blob/00d6469eafdd4aac346a0b598184c15f2560dbe5/sympy/physics/quantum/shor.py#L30-L83"><span class="viewcode-link"><span class="pre">[source]</span></span></a><a class="headerlink" href="#sympy.physics.quantum.shor.CMod" title="Permalink to this definition">¶</a></dt>
<dd><p>A controlled mod gate.</p>
<p>This is black box controlled Mod function for use by shor’s algorithm.
TODO: implement a decompose property that returns how to do this in terms
of elementary gates</p>
<dl class="py property">
<dt class="sig sig-object py" id="sympy.physics.quantum.shor.CMod.N">
<em class="property"><span class="pre">property</span> </em><span class="sig-name descname"><span class="pre">N</span></span><a class="headerlink" href="#sympy.physics.quantum.shor.CMod.N" title="Permalink to this definition">¶</a></dt>
<dd><p>N is the type of modular arithmetic we are doing.</p>
</dd></dl>

<dl class="py property">
<dt class="sig sig-object py" id="sympy.physics.quantum.shor.CMod.a">
<em class="property"><span class="pre">property</span> </em><span class="sig-name descname"><span class="pre">a</span></span><a class="headerlink" href="#sympy.physics.quantum.shor.CMod.a" title="Permalink to this definition">¶</a></dt>
<dd><p>Base of the controlled mod function.</p>
</dd></dl>

<dl class="py property">
<dt class="sig sig-object py" id="sympy.physics.quantum.shor.CMod.t">
<em class="property"><span class="pre">property</span> </em><span class="sig-name descname"><span class="pre">t</span></span><a class="headerlink" href="#sympy.physics.quantum.shor.CMod.t" title="Permalink to this definition">¶</a></dt>
<dd><p>Size of 1/2 input register.  First 1/2 holds output.</p>
</dd></dl>

</dd></dl>

<dl class="py function">
<dt class="sig sig-object py" id="sympy.physics.quantum.shor.period_find">
<span class="sig-prename descclassname"><span class="pre">sympy.physics.quantum.shor.</span></span><span class="sig-name descname"><span class="pre">period_find</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">a</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">N</span></span></em><span class="sig-paren">)</span><a class="reference external" href="https://github.com/sympy/sympy/blob/00d6469eafdd4aac346a0b598184c15f2560dbe5/sympy/physics/quantum/shor.py#L121-L171"><span class="viewcode-link"><span class="pre">[source]</span></span></a><a class="headerlink" href="#sympy.physics.quantum.shor.period_find" title="Permalink to this definition">¶</a></dt>
<dd><p>Finds the period of a in modulo N arithmetic</p>
<p>This is quantum part of Shor’s algorithm. It takes two registers,
puts first in superposition of states with Hadamards so: <code class="docutils literal notranslate"><span class="pre">|k&gt;|0&gt;</span></code>
with k being all possible choices. It then does a controlled mod and
a QFT to determine the order of a.</p>
</dd></dl>

<dl class="py function">
<dt class="sig sig-object py" id="sympy.physics.quantum.shor.shor">
<span class="sig-prename descclassname"><span class="pre">sympy.physics.quantum.shor.</span></span><span class="sig-name descname"><span class="pre">shor</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">N</span></span></em><span class="sig-paren">)</span><a class="reference external" href="https://github.com/sympy/sympy/blob/00d6469eafdd4aac346a0b598184c15f2560dbe5/sympy/physics/quantum/shor.py#L86-L103"><span class="viewcode-link"><span class="pre">[source]</span></span></a><a class="headerlink" href="#sympy.physics.quantum.shor.shor" title="Permalink to this definition">¶</a></dt>
<dd><p>This function implements Shor’s factoring algorithm on the Integer N</p>
<p>The algorithm starts by picking a random number (a) and seeing if it is
coprime with N. If it isn’t, then the gcd of the two numbers is a factor
and we are done. Otherwise, it begins the period_finding subroutine which
finds the period of a in modulo N arithmetic. This period, if even, can
be used to calculate factors by taking a**(r/2)-1 and a**(r/2)+1.
These values are returned.</p>
</dd></dl>

</section>


            <div class="clearer"></div>
          </div>
        </div>
      </div>
      <div class="sphinxsidebar" role="navigation" aria-label="main navigation">
        <div class="sphinxsidebarwrapper">
            <p class="logo"><a href="../../../index.html">
              <img class="logo" src="../../../_static/sympylogo.png" alt="Logo"/>
            </a></p>
  <h4>Previous topic</h4>
  <p class="topless"><a href="qubit.html"
                        title="previous chapter">Qubit</a></p>
  <h4>Next topic</h4>
  <p class="topless"><a href="piab.html"
                        title="next chapter">Particle in a Box</a></p>
  <div role="note" aria-label="source link">
    <h3>This Page</h3>
    <ul class="this-page-menu">
      <li><a href="../../../_sources/modules/physics/quantum/shor.rst.txt"
            rel="nofollow">Show Source</a></li>
    </ul>
   </div>
<div id="searchbox" style="display: none" role="search">
  <h3 id="searchlabel">Quick search</h3>
    <div class="searchformwrapper">
    <form class="search" action="https://docs.sympy.org/latest/search.html" method="get">
      <input type="text" name="q" aria-labelledby="searchlabel" autocomplete="off" autocorrect="off" autocapitalize="off" spellcheck="false"/>
      <input type="submit" value="Go" />
    </form>
    </div>
</div>
<script>$('#searchbox').show(0);</script>
        </div>
      </div>
      <div class="clearer"></div>
    </div>
    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../../../genindex.html" title="General Index"
             >index</a></li>
        <li class="right" >
          <a href="../../../py-modindex.html" title="Python Module Index"
             >modules</a> |</li>
        <li class="right" >
          <a href="piab.html" title="Particle in a Box"
             >next</a> |</li>
        <li class="right" >
          <a href="qubit.html" title="Qubit"
             >previous</a> |</li>
        <li class="nav-item nav-item-0"><a href="../../../index.html">SymPy 1.9 documentation</a> &#187;</li>
          <li class="nav-item nav-item-1"><a href="../../index.html" >SymPy Modules Reference</a> &#187;</li>
          <li class="nav-item nav-item-2"><a href="../index.html" >Physics</a> &#187;</li>
          <li class="nav-item nav-item-3"><a href="index.html" >Quantum Mechanics</a> &#187;</li>
        <li class="nav-item nav-item-this"><a href="#">Shor’s Algorithm</a></li> 
      </ul>
    </div>
    <div class="footer" role="contentinfo">
        &#169; Copyright 2021 SymPy Development Team.
      Last updated on Sep 30, 2021.
      Created using <a href="https://www.sphinx-doc.org/">Sphinx</a> 4.1.2.
    </div>
  </body>

<!-- Mirrored from docs.sympy.org/latest/modules/physics/quantum/shor.html by HTTrack Website Copier/3.x [XR&CO'2014], Sat, 15 Jan 2022 03:27:47 GMT -->
</html>